package com.xyhuo.leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class CombinationSum3 {

    public List<List<Integer>> combinationSum3(int k, int n) {
        cal(k, n, new HashSet<>(), 1);
        return ans;
    }

    public static void main(String[] args) {
        CombinationSum3 c = new CombinationSum3();
        List<List<Integer>> ans = c.combinationSum3(3, 9);
        System.out.println(ans.size());
    }

    private List<List<Integer>> ans = new ArrayList<>();

    private void cal(int k, int n, Set<Integer> set, int start) {
        if (k == 0) {
            if (n == 0) {
                List<Integer> li = new ArrayList<>();
                li.addAll(set);
                ans.add(li);
            }
            return;
        }
        for (int i = start; i <= 9; i++) {
            if (set.contains(i)) {
                continue;
            }
            set.add(i);
            cal(k - 1, n - i, set, i + 1);
            set.remove(i);
        }
    }
}
